#! /usr/bin/env python
# -*- coding: utf-8 -*-

class KmpMatch():
    EMPTY = ''

    def kmp_match(self, src, target):
        if src is None or target is None:
            return -1

        if target == self.EMPTY:
            return 0

        if src == self.EMPTY:
            return -1

        self.src,     self.target = src, target
        self.src_len, self.tar_len = len(src), len(target)

        self.next_table = self.kmp_compile_target()
        return self.match_compilted_target()

    # =================== compiled match =====================
    def match_compilted_target(self):
        match_from = 0

        while self.src_len - match_from >= self.tar_len:
            match_len = self.calc_match_len(match_from)
            if match_len == self.tar_len:
                return match_from
            else:
                match_from += self.next_table[match_len]

        return -1

    def calc_match_len(self, match_from):
        assert self.src_len - match_from >= self.tar_len
        match_len = 0

        for i in range(self.tar_len):
            if self.src[match_from + i] == self.target[i]:
                match_len += 1
            else:
                break

        return match_len

    # =================== compiling =====================
    def kmp_compile_target(self):
        ''' 计算匹配长度为0到长度为 len(target)-1 的子串的:
            最长移动长度 == 子串长度-最长相同前缀长度

            返回值: next_table

            示例:
            target = 'abcabc__', 匹配到'abcabc'前6位, 下次移动3位即可

            TODO:
            这里可以返回一个list, index是天然的key, 但是为了程序更易读, 使用dict
        '''
        assert self.tar_len >= 1

        # next_table = {}               # (sub_match_len, move_len)
        next_table = [0] * self.tar_len # (sub_match_len, move_len)
        next_table[0] = 1               # 如果没有匹配字符, 必须移动到下一位
        if self.tar_len > 1:
            next_table[1] = 1               # 如果只匹配到1位字符, 必须移动到下一位

        # 2 --> tar_len-1 (NOTE: tar_len无意义, 因为表示全匹配)
        for sub_match_len in range(2, self.tar_len):
            sub_match_str = self.target[:sub_match_len]
            max_same_pre_len = self.max_pre_len(sub_match_str, next_table)
            move_len = sub_match_len - max_same_pre_len
            next_table[sub_match_len] = move_len

        return next_table

    @staticmethod
    def max_pre_len(s, next_table=None):
        '''
            s_len - 1 ------> 1
            从最长开始匹配
            for sub_len in range(s_len-1, 0, -1):
        '''
        # TODO: 优化s的max_pre_len 可以在前一次s-1的基础上来计算
        s_len = len(s)
        assert s_len >= 2      # s_len == 1无意义

        max_pre_len = s_len - 1
        if next_table:
            last_s_len = s_len - 1
            last_move = next_table[s_len-1]
            last_pre_len = last_s_len - last_move
            max_pre_len = last_pre_len + 1

        for sub_len in range(max_pre_len, 0, -1):
            if s[:sub_len] == s[-sub_len:]:
                return sub_len

        return 0


# =================== solution  =====================
class Solution:
    def strStr(self, source, target):
        kmp = KmpMatch()
        return kmp.kmp_match(source, target)


def main():
    print("start main")

if __name__ == "__main__":
    main()
